package solution;

import java.util.LinkedList;
import java.util.Scanner;

/**
 * <a href="https://www.nowcoder.com/study/live/717/4/5">
 * 单调栈结构 - 牛客网 - 课程</a>
 *
 * @author or2
 * @Description 给定一个不含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。
 * @create 2021年09月09日 时间: 11:26
 */
public class MonotonousStack {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int totalNums = scanner.nextInt();
//        将数据信息全部读出到数组中
        int[] arr = new int[totalNums];
        for (int i = 0; i < totalNums; i++) {
            arr[i] = scanner.nextInt();
        }

//        辅助单调栈 - 存放数组下标
        LinkedList<Integer> stackAux = new LinkedList<>();
//        辅助二维数组, 存放答案
        int[][] ans = new int[totalNums][2];
        for (int i = 0; i < arr.length; i++) {
//            堆栈为空, 直接压入
            if (stackAux.isEmpty()) {
                stackAux.push(i);
                continue;
            }
//            同栈顶下标指示的元素比较
            if (arr[i] > arr[stackAux.peek()]) {
                stackAux.push(i);
                continue;
            }
//            小于栈顶元素, 出栈
            while (arr[i] < arr[stackAux.peek()]) {
                Integer popIndex = stackAux.pop();
                ans[popIndex][1] = i;
                ans[popIndex][0] = stackAux.isEmpty() ? -1 : stackAux.peek();
                if (stackAux.isEmpty()) {
                    stackAux.push(i);
                    break;
                }
            }

//            当前元素入栈
            stackAux.push(i);
        }

//        处理栈中剩余元素
        while (!stackAux.isEmpty()) {
            Integer popIndex = stackAux.pop();
            ans[popIndex][0] = stackAux.isEmpty() ? -1 : stackAux.peek();
            ans[popIndex][1] = -1;
        }

//        输出答案
        for (int[] an : ans) {
            System.out.println(an[0] + " " + an[1]);
        }
    }
}
